As basic data structures used by application programs, database systems, or the like, there are known structures referred to as an associative array, KeyValue Store, Map, and a storage engine acquiring a value from a key. Further, such data structures are categorized into a data structure where a key is ordered by a value thereof and a data structure where a key is stored without being ordered. In the configuration where no ordering is performed, a data storage destination of a key is determined based on a value obtained by hashing the key. On the other hand, in the configuration where ordering is performed, each storage destination is associated with has a value range for handling as a value range data unit and then a data storage destination is determined from the value range data unit and a key.
NPL 1 proposes one example of a value range management method in an information system. In the example of NPL 1, a system referred to as Bigtable includes tablet servers storing a plurality of data units, a Bigtable master, Chubby that is a centralized server, metadata⋅tablet servers, and clients. Each tablet server stores a data unit of a certain continuous value range as a tablet. The Bigtable master manages, by a B+Tree, in which tablet server a tablet is stored, stores a plurality of partial trees configuring the B+Tree on a plurality of metadata⋅tablet servers, and stores a partial tree corresponding to a root on Chubby. When a tablet managed by the tablet server is changed, this change is notified to the master. A client accessing this Bigtable acquires the root of the B+Tree by accessing Chubby and then acquires a partial tree thereof from the metadata⋅tablet server to be cached. While this cache is effective, the client can identify locally a tablet server corresponding to a key value. When a tablet handled by the tablet server is changed, the cache on the client becomes invalid, but it is not until the client accesses the tablet server corresponding to the key value that the client detects this invalidity and then makes an inquiry to the metadata⋅tablet server about valid information.
NPL 2 proposes another example of the value range management method. In the example of NPL 2, a system referred to as Baton includes a plurality of P2P (Peer to Peer) nodes. Each node stores data units having a continuous value range. Each node has a link relationship with another node and this link relationship forms a balanced tree as a whole. Each node includes a link to a node corresponding to a parent node in the tree structure, a link to a node corresponding to a child node, and links to adjacent nodes of the same layer. Regarding the links to the adjacent nodes of the same layer, a value range with respect to each link destination is also managed. Upon having acquired an access request for a given value, a certain node determines which one of the value ranges handled by the adjacent nodes in the same layer includes the value, and then transfers the access request to the determined node. When the node of the transfer destination continues similar processing, a node holding a data unit corresponding to the value is detected. A link relationship among nodes is sequentially changed to maintain the balanced tree when a node is newly added or a node leaves. Further, when a distribution of stored data units is distorted due to non-uniformity among nodes, each node changes a value range and a link relationship so as to uniform the data distribution.